package com.mlamp.动态规划;

public class 最大子数组问题 {
    public static void main(String[] args) {

        int[] input = new int[]{
                -2, 1, -3, 4, -1, 2, 1, -5, 4
        };
        int sum = maxSubArray(input);
        System.out.println(sum);

        sum = maxSubArray2(input);
        System.out.println(sum);

        sum = maxSubArrayA(input);
        System.out.println(sum);

    }


    public static int maxSubArrayA(int[] array){
        if (array == null || array.length < 1) throw  new IllegalArgumentException("array given is valid");
        int result[] = new int[array.length];
        int res = 0;
        result[0] = array[0];
        for (int i = 1; i < array.length ; i++) {
            result[i] = Math.max(result[i-1] + array[i], array[i]);
            res = Math.max(result[i], res);
        }
        return res;
    }


    private static int maxSubArray2(int[] array) {
        if (array == null || array.length < 1) throw new IllegalStateException("array given is empty");
        int result[] = new int[array.length];
        int res = 0;
        result[0] = array[0];
        for (int i = 1; i < array.length; i++) {
            result[i] = Math.max(result[i - 1] + array[i], array[i]);
            res = Math.max(res, result[i]);
        }
        return res;
    }


    private static int maxSubArray(int[] array) {
        int length = array.length;
        if (length == 0) return 0;
        int[] dp = new int[length];
        dp[0] = array[0];
        for (int i = 1; i < length; i++) {
            dp[i] = Math.max(array[i], dp[i - 1] + array[i]);
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            res = Math.max(res, dp[i]);
        }

        return res;
    }


}
